\chapter{Вопрос №3}

Понятие $k$-перестановки из $n$-элементов (с повторениями и без повторений), их количество. Количество подмножеств данного множества. Рекуррентное соотношение для $k$-перестановок без повторений; формальное и комбинаторное доказательства. Связь количества $k$-перестановок и $k$-сочетаний без повторений. Урновые схемы для $k$-сочетний и $k$-перестановок.

\section{$k$-перестановка из $n$-элементов}

Пусть есть $n$-множество $$ X = \left\{x_1, x_2, ... x_n\right\} $$, упорядоченный набор $$ \left(a_1, a_2, ..., a_k\right) $$ элементов этого множества называется $k$ - перестановкой из $n$-элементов (а также кортежем, строкой, размещением, упорядоченной выборкой). Если допускаются повторения элементов, то говорять о $k$-перестановке из $n$ с повторениями.

Количество $k$-перестановок с повторениями из $n$ очевидно равно $$ n^k $$, для перестановок без повторений $$ \Lowerfact{n}{k} $$

\section{Рекуррентное соотношение}
Если обозначить число $k$-перестановок без повторений из $n$ через $P\left(n,k\right)$, то можно сформулировать рекуррентное соотношение:
\begin{equation}
	P\left(n,k\right) = P\left(n-1,k\right) + kP\left(n-1,k-1\right)
\end{equation}
при начальных условиях:
\[
	\begin{split}
		& P\left(n,0\right) = 1\\
		& P\left(n,k\right) = 0, k > n
	\end{split}
\]
\begin{Proof} (Комбинаторное). Разбиваем все перестановки на два блока:
\begin{enumerate}
\item В первый блок попадают перестановки в которых нет элемента $n$. Число таких перестановок равно $$ P\left(n-1,k\right) $$

\item Во второй блок входят перестановки, в которых присутствует элемент $n$. Так как этот элемент может быть расположен на любом из $k$ мест получаем, что общее число таких перестановок $$ kP\left(n-1,k-1\right) $$
\end{enumerate}
\end{Proof}

\begin{Proof} (Не комбинаторное).
\[
	\begin{split}
		& P\left(n,k\right) = \prod_{i=0}^{k-1}\left(n-i\right) = n\prod_{i=1}^{k-1}\left(n-i\right) = n\prod_{i=0}^{k-2}\left(n-1-i\right) = \\
		& = \left(n-k+k\right)\prod_{i=0}^{k-2}\left(n-1-i\right) = \left(n-k\right)\prod_{i=0}^{k-2}\left(n-1-i\right) + k\prod_{i=0}^{k-2}\left(n-1-i\right) = \\
		& = P\left(n-1,k\right) + kP\left(n-1,k-1\right)
	\end{split}
\]
\end{Proof}

\section{Связь сочетаний и перестановок}

\begin{equation}
	\binom{n}{k} = \frac{\Lowerfact{n}{k}}{k!}
\end{equation}
Комбинаторный смысл - число способов выбрать $k$-подмножество из $n$-множества $$ \binom{n}{k} $$, а упорядочить элементы подмножества можно $k!$ спосбоами итого:
\[
	\Lowerfact{n}{k} = k! \binom{n}{k}
\]
